package com.sheng.leetcode.year2023.month03.day06;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/06
 * <p>
 * 1653. 使字符串平衡的最少删除次数<p>
 * <p>
 * 给你一个字符串 s ，它仅包含字符 'a' 和 'b'  。<p>
 * 你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，<p>
 * 且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。<p>
 * 请你返回使 s 平衡 的 最少 删除次数。<p>
 * <p>
 * 示例 1：<p>
 * 输入：s = "aababbab"<p>
 * 输出：2<p>
 * 解释：你可以选择以下任意一种方案：<p>
 * 下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），<p>
 * 下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。<p>
 * <p>
 * 示例 2：<p>
 * 输入：s = "bbaaaaabb"<p>
 * 输出：2<p>
 * 解释：唯一的最优解是删除最前面两个字符。<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length <= 10^5<p>
 * s[i] 要么是 'a' 要么是 'b'  。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-deletions-to-make-string-balanced">1653. 使字符串平衡的最少删除次数</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1653 {

    @Test
    public void test01() {
//        String s = "aababbab";
//        String s = "bbaaaaabb";
        String s = "baababbaabbaaabaabbabbbabaaaaaabaabababaaababbb";
        System.out.println(new Solution().minimumDeletions(s));
    }
}

class Solution {
    public int minimumDeletions(String s) {
        // 思路：在 a...b...a...b...，这种情况中选择被夹击的 a 和 b 并判断哪个长度更短
        // 删除完成之后一定会变成 a...b...，这种情况那么就很简单了
        int length = s.length();
        // 定义 f[i] 表示前 i 个字符中，删除最少的字符串
        int[] f = new int[length + 1];
        // 表示当前遍历的位置之前的字符中，字符 b 的个数
        int b = 0;
        for (int i = 1; i <= length; i++) {
            if (s.charAt(i - 1) == 'b') {
                // 此时不影响前 i 个字符的平衡性
                f[i] = f[i - 1];
                b += 1;
            } else {
                // 两种选择，第一种可以选择删除当前字符，那么有 f[i] = f[i - 1] + 1
                // 第二种也可以选择删除之前的字符 b，那么有 f[i] = b，两者取最小值即可
                f[i] = Math.min(f[i - 1] + 1, b);
            }
        }
        return f[length];
//        int num = 0;
//        List<String> list = new ArrayList<>();
//        char c = 0;
//        int n = 0;
//        for (int i = 0; i < s.length(); i++) {
//            if (i == 0) {
//                n = 0;
//                c = s.charAt(i);
//            } else if (s.charAt(i) != c) {
//                list.add(s.substring(n, i));
//                if (i != s.length() - 1) {
//                    n = i;
//                    c = s.charAt(i);
//                } else {
//                    list.add(s.substring(i));
//                }
//            }
//        }
//        for (int i = 0; i < list.size(); i++) {
//            if (list.get(i).contains("b") && i != list.size() - 1) {
//                num += Math.min(list.get(i).length(), list.get(i + 1).length());
//            }
//        }
//        return num;
    }
}
